import bisect
from typing import List


class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        # ---------- 坐标压缩 ----------
        # 时间复杂度：O(NlogN)
        rooms.sort()
        index = [room_id for room_id, size in rooms]

        # ---------- 构造树状数组 ----------
        # 每个中间结点均为其包含子结点的最大值
        # 时间复杂度：O(N)
        # 计算叶结点
        size = 2 ** len(rooms).bit_length() - 1
        tree = [0] * (2 * size)
        for i in range(len(rooms)):
            tree[size + i] = rooms[i][1]

        # 计算中间结点
        for i in range(size - 1, -1, -1):
            tree[i] = max(tree[i * 2 + 1] if i * 2 + 1 < size * 2 else 0,
                          tree[i * 2 + 2] if i * 2 + 2 < size * 2 else 0)

        # 计算树状数组最左侧结点列表
        left_node_lst = [0]
        while left_node_lst[-1] < size * 2:
            left_node_lst.append(left_node_lst[-1] * 2 + 1)

        # 计算树状数组最右侧结点列表
        right_node_lst = [0]
        while right_node_lst[-1] < size * 2:
            right_node_lst.append(right_node_lst[-1] * 2 + 2)

        # print("树状数组:", tree, "最左侧结点列表:", left_node_lst, "最右侧结点列表:", right_node_lst)

        # ---------- 计算查询结果 ----------
        ans = []
        for preferred, min_size in queries:
            # ----- 处理没有满足条件的房间的情况 -----
            if tree[0] < min_size:
                ans.append(-1)
                continue
            # 当前可保证：tree[0] >= min_size

            # ----- 计算偏爱房间对应的压缩下标位置 -----
            right = bisect.bisect_left(index, preferred)  # 大于等于偏爱房间下标的房间
            # print(index, preferred, "->", right)

            # ----- 向左寻找最靠近的符合条件的房间 -----
            left = (right - 1) + size  # 计算左偏爱房间的叶结点坐标

            if right > 0:  # 处理偏爱房间有左侧房间的情况
                # 向上寻找：寻找包含子结点的最大值超过目标值的结点
                while tree[left] < min_size:  # 不断向上，直到找到超过目标值的结点
                    if left % 2 == 1:  # 当前结点是左子结点
                        if left in left_node_lst:  # 当前结点已经是最左侧结点的情况
                            break
                        left = (left - 1) // 2 - 1
                    else:  # 当前结点是右子结点
                        left = (left - 2) // 2

                # 在左侧找到符合条件的房间的情况
                if tree[left] >= min_size:
                    # 向下寻找：寻找当前结点范围内，超过目标值位置的最右侧位置
                    while left < size:  # 不断向下，直到找到叶结点
                        if tree[left * 2 + 2] >= min_size:
                            left = left * 2 + 2
                        else:
                            left = left * 2 + 1

                # 没有在左侧找到符合条件的房间的情况
                else:
                    left = size

            else:
                left = size

            # ----- 向右寻找最靠近的符合条件的房间 -----
            if right < size:  # 处理偏爱房间有右侧房间的情况
                right += size  # 计算右偏爱房间的叶结点坐标

                # 向上寻找：寻找包含子结点的最大值超过目标值的结点
                while tree[right] < min_size:  # 不断向上，直到找到超过目标值的结点
                    if right % 2 == 1:  # 当前结点是左子结点
                        right = (right - 1) // 2
                    else:  # 当前结点是右子结点
                        if right in right_node_lst:  # 当前结点已经是最右侧结点的情况
                            break
                        right = (right - 2) // 2 + 1

                # 在右侧找到符合条件的房间的情况
                if tree[right] >= min_size:
                    # 向下寻找：寻找当前结点范围内，超过目标值位置的最左侧位置
                    while right < size:  # 不断向下，直到找到叶结点
                        if tree[right * 2 + 1] >= min_size:
                            right = right * 2 + 1
                        else:
                            right = right * 2 + 2

                # 没有在右侧找到符合条件的房间的情况
                else:
                    right = size + len(rooms) - 1

            else:
                right = size + len(rooms) - 1

            # print("查询信息:", preferred, min_size, "左、右侧最近房间:", left, right, "->", rooms[left - size], rooms[right - size])

            # ----- 寻找最靠近的符合条件的房间 -----
            # 计算左右房间实际信息
            left_room, left_size = rooms[left - size]
            right_room, right_size = rooms[right - size]

            # 左侧和右侧均找到符合条件的房间的情况
            if left_size >= min_size and right_size >= min_size:
                if abs(preferred - left_room) <= abs(preferred - right_room):
                    ans.append(left_room)
                else:
                    ans.append(right_room)

            elif left_size >= min_size:
                ans.append(left_room)

            elif right_size >= min_size:
                ans.append(right_room)

            else:  # 原则上不会出现这种情况
                ans.append(-1)

        return ans


if __name__ == "__main__":
    # [3,-1,3]
    print(Solution().closestRoom(rooms=[[2, 2], [1, 2], [3, 2]],
                                 queries=[[3, 1], [3, 3], [5, 2]]))

    # [2,1,3]
    print(Solution().closestRoom(rooms=[[1, 4], [2, 3], [3, 5], [4, 1], [5, 2]],
                                 queries=[[2, 3], [2, 4], [2, 5]]))

    # 自制用例:[1]
    print(Solution().closestRoom([[1, 3], [5, 3]], [[3, 3]]))  # 1

    # 自制用例:[3]
    print(Solution().closestRoom(rooms=[[1, 4], [2, 3], [3, 5], [4, 1], [5, 2]],
                                 queries=[[5, 3]]))
